package com.ztom.daily.n2022.m3;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 子数组范围和
 * <p>
 * https://leetcode-cn.com/problems/sum-of-subarray-ranges/
 *
 * @author ZhangTao
 */
public class Day04SubArrayRanges {

    public long subArrayRanges1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            int min = nums[i];
            int max = nums[i];
            for (int j = i; j < nums.length; j++) {
                min = Math.min(min, nums[j]);
                max = Math.max(max, nums[j]);
                sum += max - min;
            }
        }
        return sum;
    }

    /**
     * 单调栈
     * <p>
     * 以 i 位置为最小值, 通过单调栈得到范围 (k, j)
     * Y    X    Z
     * k .. i .. j
     * <p>
     * 可以得到以 X 为最小值的子数组个数: (i - k) * (j - i)
     */
    public long subArrayRanges(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        long sum = 0;

        // i 位置作为最小值出现的次数
        long[] min = calculateCount(nums, true);

        // i 位置作为最大值出现的次数
        long[] max = calculateCount(nums, false);

        for (int i = 0; i < nums.length; i++) {
            sum += (max[i] - min[i]) * nums[i];
        }

        return sum;
    }

    private long[] calculateCount(int[] nums, boolean isMini) {
        int n = nums.length;
        long[] res = new long[n];

        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() &&
                    (isMini ?
                            nums[stack.peekLast()] >= nums[i] :
                            nums[stack.peekLast()] <= nums[i]
                    )
            ) {
                Integer j = stack.pollLast();
                int l = stack.isEmpty() ? -1 : stack.peekLast();
                int r = i;
                res[j] = (long) (j - l) * (r - j);
            }
            stack.addLast(i);
        }
        // 结算剩余的
        while (!stack.isEmpty()) {
            Integer j = stack.pollLast();
            int l = stack.isEmpty() ? -1 : stack.peekLast();
            int r = n;
            res[j] = (long) (j - l) * (r - j);
        }

        return res;
    }
}
